//设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单
//词存在于已构建的神奇字典中。 
//
// 实现 MagicDictionary 类： 
//
// 
// MagicDictionary() 初始化对象 
// void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字
//符串互不相同 
// bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得
//所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。 
// 
//
// 
//
// 
// 
// 
// 示例： 
// 
// 
// 
//
// 
//输入
//inputs = ["MagicDictionary", "buildDict", "search", "search", "search", 
//"search"]
//inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], [
//"leetcoded"]]
//输出
//[null, null, false, true, false, false]
//
//解释
//MagicDictionary magicDictionary = new MagicDictionary();
//magicDictionary.buildDict(["hello", "leetcode"]);
//magicDictionary.search("hello"); // 返回 False
//magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
//magicDictionary.search("hell"); // 返回 False
//magicDictionary.search("leetcoded"); // 返回 False
// 
//
// 
//
// 提示： 
//
// 
// 1 <= dictionary.length <= 100 
// 1 <= dictionary[i].length <= 100 
// dictionary[i] 仅由小写英文字母组成 
// dictionary 中的所有字符串 互不相同 
// 1 <= searchWord.length <= 100 
// searchWord 仅由小写英文字母组成 
// buildDict 仅在 search 之前调用一次 
// 最多调用 100 次 search 
// 
//
// 
//
// 
// 注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-
//dictionary/ 
//
// Related Topics 深度优先搜索 设计 字典树 哈希表 字符串 👍 54 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-02-26 21:57:03
 * @description LCR 064.实现一个魔法字典
 */
public class US1pGT{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 US1pGT fun=new US1pGT();


	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class MagicDictionary {
         Trie dict;

    /** Initialize your data structure here. */
    public MagicDictionary() {
            dict=new Trie();
    }
    
    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            dict.insert(s);
        }
    }
    
    public boolean search(String searchWord) {
        return dict.search(searchWord);
    }
    class Trie{
        Trie [] ne;
        boolean end;
        Trie(){
            ne=new Trie[26];
            end=false;
        }
        void insert(String  word){
            Trie p=this;
            for (char c : word.toCharArray()) {
                int ind=c-'a';
                if(p.ne[ind]==null){
                    p.ne[ind]=new Trie();
                }
                p=p.ne[ind];
            }
            p.end=true;
        }
        boolean search(String word){
            Trie p=this;
          return   dfs(false,0,word,p);
        }
        boolean dfs(boolean changed,int ind,String word,Trie node){
            if(ind==word.length()) return changed&&node.end;
            char c = word.charAt(ind);
            boolean res=false;
            if(changed) {
                // 如果已经替换过字符，只能继续匹配当前字符
                if(node.ne[c-'a']!=null){
                    res |= dfs(changed, ind + 1, word, node.ne[c-'a']);
                }
            } else{
                // 如果没有替换过字符，可以尝试替换当前字符
                for (int i = 0; i < 26; i++) {
                    if(node.ne[i]!=null) {
                        res |= dfs(i!=c-'a', ind + 1, word, node.ne[i]);
                    }
                }
            }

            return res;
        }
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
